GRACE TECHNICAL REPORTS
An Algebraic Approach to Bidirectional Model
Transformation
S. Hidaka
Z. Hu
H. Kato
K. Nakano
GRACE-TR-2008–02
September 2008
CENTER FOR GLOBAL RESEARCH IN
ADVANCED SOFTWARE SCIENCE AND ENGINEERING
NATIONAL INSTITUTE OF INFORMATICS
2-1-2 HITOTSUBASHI, CHIYODA-KU, TOKYO, JAPAN
An Algebraic Approach to Bidirectional Model Transformation
Soichiro Hidaka
Zhenjiang Hu
Hiroyuki Kato
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku
Tokyo 101-8430, Japan
{
hidaka,hu,kato
}
@nii.ac.jp
Keisuke Nakano
The University of Electro-Communications
1-5-1 Chofugaoka, Chofu-shi
Tokyo 182-8585, Japan
[email protected]
Abstract
Bidirectional model transformation plays an important role in maintaining consistency between two models, and has many potential applications in software development, including model synchronization, round-trip engineering, software evolution, multiple-view software development, and reverse engineering. However, unclear bidirectional semantics, weak bidirectionalization method, and lack of systematic development framework are known problems that prevent it from being practically used. To remedy this situation, in this paper, we propose a novel algebraic frame-work for bidirectional model transformation, by integrat-ing the state-of-the-art technologies on bidirectional tree transformations and algebraic graph querying. We make a significant extension from bidirectional tree transformation to bidirectional graph transformation, and give a power-ful automatic bidirectionalization method to derive a back-ward graph transformation from a forback-ward graph trans-formation. Moreover, we demonstrate how our algebraic framework can support systematic development of efficient large-scale bidirectional model transformations in a com-positional manner. Our experimental results show promise of the new approach.
1
Introduction
Model transformation plays an important role in model-driven software development, which aims to introduce sig-nificant efficiency and rigor to the theory and practice of software development. In model-driven software develop-ment, models are the key artifacts in all phases of devel-opment, from system specification and analysis, to design and testing. The use of models and the application of model transformations open up new possibilities for creating, ana-lyzing, and manipulating systems through various types of tools and languages.
Bidirectional model transformation [25, 2], being
an enhancement of model transformation with bidirec-tional capability, is an important requirement on OMG’s Queries/Views/Transformations (QVT) standard [22] rec-ommended for defining model transformation languages. It describes not only a forward transformation from a source model to a target model, but also a backward transformation showing how to reflect the changes on the target model to the source model so that consistency between two models is maintained. Bidirectional model transformation has many potential applications in software development, including model synchronization [2, 27, 12], round-trip engineering [1], software evolution by keeping different models coher-ent to each other [20, 8], multiple-view software develop-ment [13, 11], and traceability and reverse engineering [5]. Despite these promising uses of bidirectional model transformation in software development, there are still very few serious practical applications in which bidirectional model transformation is actually used. There are three known problems.
First, there is uncertainty over fundamental semantics of bidirectional transformation. As strongly argued in [25], there lacks a clear definition of what bidirectional model transformation means. In practice, a model transformation may not be bijective, so its backward model transformation should not be defined merely as an inverse of forward model transformation. However, if there is no clear semantics of bidirectional transformation or backward transformation is not guaranteed to work without harm, no one would seri-ously use it in their systems.
Figure 1. An Algebraic Framework for Bidi-rectional Model Transformation Framework
the source and target models can be transformed back and forth.
Third, and very important, there lacks a systematic way to develop bidirectional model transformation in large. As indicated in the conclusion in [9], most model transforma-tion languages [9, 7] based on graph transformatransforma-tions have weak composition mechanism, which makes them hard to support systematic development of model transforma-tions in the large [18]. The existing examples of bidirec-tional model transformations are somehow too simple to show both challenges and advantages of bidirectional model transformation.
In this paper, we propose a novel algebraic framework for bidirectional model transformation to solve these prob-lems, by integrating two state-of-the-art techniques: bidi-rectional tree transformations [10, 21, 4, 16] in the program-ming language community, and the algebraic graph query-ing language UnQL [6] intensively studied in the database community. We make a significant extension from bidi-rectional tree transformation to bidirectionalgraph trans-formation, and give a powerful automatic bidirectionaliza-tion method to derive backward graph transformabidirectionaliza-tions from a forward transformation in UnQL+ [14], an extension of UnQL for graph transformation.
Figure 1 depicts an architecture of our algebraic frame-work. A model transformation is described in UnQL+,
which isfunctional(rather than rule-based as in many exist-ing tools) andcompositionalwith high modularity for reuse and maintenance. The model transformation is then desug-ared to a coregraph algebrawhich consists of a set of con-structors for building graphs and a powerful structural re-cursion for manipulating graphs. This graph algebra can have clear bidirectional semantics and be efficiently
evalu-ated in a bidirectional manner. Our main technical contri-butions can be summarized as follows.
• We made the first attempt of adapting an existing well-established graph querying language for model trans-formation, whose importance has not been recognized so far. We show that UnQL, a powerful graph querying language being suitable for systematic development of efficient graph queries, can be extended for system-atic development of useful model transformations, as demonstrated in Section 6.
• We propose the first general method for bidirectional-izinggraph transformation, although there have pro-posed several bidirectional tree transformation lan-guages. Compared with trees, the challenge here is how to deal with cycles and traversals of graphs in bidirectional computation. The key to the success of our bidirectionalization is the simple but powerful in-ternal algebra of UnQL+, where structural recursion can be computed in abulk way which is suitable for both forward and backward computation.
• We give an efficient implementation of bidirectional computation of UnQL+. We carefully record
neces-sary but least information during forward transforma-tion for later efficient backward transformatransforma-tion, and apply automatic fusion transformation to eliminate un-necessary intermediate models used in model transfor-mation composition. The core system has been imple-mented in Objective Caml with about 7,500 loc, and all the examples in this paper have been passed by the system. More application examples can be found at the system page1.
The organization of this paper is as follows. After re-viewing graph data model and structural recursion in UnQL in Section 2, we show that UnQL can be extended to UnQL+ that are suitable for developing model
transforma-tions in a compositional way in Section 3. To implement our bidirectional framework, we show how to desugar UnQL+
to a core graph algebra in Section 4, and how to implement a bidirectional evaluator for the core graph algebra with a clear bidirectional semantics and efficient implementation in Section 5. We show an application in Section 6, discuss related work in Section 7, and conclude the paper in Sec-tion 8.
2
Graph Data Model and Structural
Recur-sion on Graphs
We start with a brief explanation of graph data model and structural recursion, which are two important concepts
Figure 2. A Simple Graph
in the graph querying language UnQL [6]. They serve as the basis of our algebraic framework for model transformation.
2.1
Graph Data Model
External Graph Representation Graphs in UnQL are rooted and directed cyclic graphs with no order on outgoing edges. They are edged-labelled in the sense that all infor-mation is stored as labels on edges (the labels on nodes have no particular meaning). Figure 2 gives a small example of a directed cyclic graph with six nodes and seven edges. In text, it is represented by
g = {a:{a:g1}, b:{a:g1}, c:g2}
g1 = {d:{}}
g2 = {c:g2}
where the set{l1 : e1, . . . , ln : en}denotes a graph which
containsnedges with labelsl1, . . . , ln, each of which points
to a graph again, and the empty set{}denotes a graph with a single node. Two graphs can be merged using set union operation such asg∪g′.
As another example, consider to represent the class model diagram in Figure 3 by an edge-labelled graph. This example is from [3], which will also be used in Section 6. A class model consists of classes and directed associations between classes. A class is indicated as persistent or non-persistent. It consists of one or more attributes, at least one of which must be marked as constituting the classes’ primary key. An attribute type is of a primitive data type (e.g. String, Integer). An association specifies an inheri-tance relation between two classes. The class model in Fig-ure 3 consists of three classes and two directed associations, where each class has a primary attribute. This class model can be represented by the graph in Figure 4, where informa-tion is moved to edges.
Internal Graph Representation While the external graph representation is sufficient for users to consider when writing bidirectional model transformation, the internal graph representation is designed for internal implementa-tion and semantics descripimplementa-tion of structural recursion on
Figure 3. A Class Diagram
graphs. Different from the external representation, the inter-nal representation introduceϵedge for representing shortcut of two nodes. For instance, we have
{ϵ:{a:g1}, ϵ:{b:g2}}={a:g1, b:g2}.
As will be seen in Sections 2.2 and 5.1, the ϵedge is im-portant in defining both bulk and bidirectional semantics of structural recursion.
Another difference is that for internal composition of graphs, an internal graph may have some node marked with input or output marker, which is called input or output node, respectively. We use&x∈Marker to denote that&xis a marker. Input markers are used to select entry points of the graph, whereas output markers are used to connect with other input nodes later.
Graph Bisimulation Graph bisimulation defines value equalities between graph instances. Intuitively, when graph
G1 and G2 are bisimilar, then every node x1 in G1 has
a counterpart x2 in G2, and if there is an edge formx1
to y1, then there is a corresponding edge from x2 to y2.
UnQL data model extends graph bisimulation by (1) requir-ing equalities between labels, (2) allowrequir-ing insertion of one or more consecutiveϵedges between normal edge and tar-get node (y1ory2above), (3) requiring correspondence
be-tween input nodes inG1andG2, (4) requiring
correspon-dence between output markers of corresponding nodes (out-put markers may be associated with the node other than cor-responding nodes, provided that the marker is associated with nodes that can be reached by traversingϵedges).
The notion of extended bisimulation is useful because it allows variation in representing semantically equivalent graphs. It has been shown that a graph transformation de-fined in UnQL preserves bisimilarity [6]. If two graphsG1
Figure 4. A Class Model Represented by an Edge-Labelled Graph
andG2are bisimilar,f(G1)andf(G2)are bisimilar for any
transformationf in UnQL.
2.2
Structural recursion in UnQL
Structural recursion plays a significant role in our frame-work for description of graph transformation, bidirectional-ization, and optimization. As will be shown in Section 4, any graph transformation in UnQL and its extension (Sec-tion 3) can be described in terms of structural recursion.
2.2.1 Structural Recursion
Structural recursive functionfin UnQL is a recursive com-putation scheme on graphs defined as follows, where⊙is a given binary operator.
f({}) = {}
f({l:g}) = l⊙f(g) f(g1∪g2) = f(g1)∪f(g2)
Different choices of⊙defines different functions, and for simplicity we abbreviate the above definition as follows.
sfun f({l:g}) =l⊙f(g)
Note that for a graphgwhich may contain cycles, the com-putation off(g)always terminates under the usual recur-sive semantics: remember all recurrecur-sive calls and reuse their result to avoid entering infinite loops.
As a simple example, we may use the following struc-tural recursion to replace all edges labelledabydand delete the edges labeledcfor the graph in Figure 2.
sfun a2d xc({l:g}) = ifl=athen{d:f(g)}
else ifl=cthenf(g)
else{l:f(g)}
A natural extension of the above structural recursion is to allow mutual recursion, because any mutually defined func-tions can be merged into one by the standard tupling trans-formation [15]. The following mutually defined structural recursive functionrelabelcan replace all labelsnameunder primitiveDataTypewithtypeNamein Figure 4 .
sfun relabel({primitiveDataType:g}) ={primitiveDataType:addT(g)} | relabel({l:g}) ={l:relabel(g)}
sfun addT({name:g}) ={typeName:addT(g)} | addT({l:g}) ={l:addT(g)}
2.2.2 Bulk Semantics
One important feature of a structural recursive function is that it can be computed in abulkmanner (calledbulk seman-tics[6]), which make it possible for our bidirectionalization (Section 5.1) and automatic optimization (Section 5.2).
Given a structural recursive function defined by
1
S12 S13 S14
E12 d
E13 b
E14
2 3 4
S25 S35
S44
E25 d
5
S56 E35
d
E44
E56 d
6
Figure 5. A Simple Edge-labelled Graph
the computation off on a graph can be performed by the following three steps: (1) applying to each edge the follow-ing function
fe(l) =l⊙&z
where&zdenotes a node with an output marker&zwhich will be connected with other nodes later, (2) marking the root node of the result graph with the input marker&z, and (3) joining the results with theϵedge.
To be concrete, consider to apply the structural recur-sive functiona2d xcto the graph in Figure 2. Applying the function to each edge fromitojgives a subgraph contain-ing a graph with an edge fromSijtoEij(where the dotted edge denotes anϵedge), then marking the root with an input marker, and finally joining the nodes withϵedges according to the original graph shape and input/out markers yields the graph in Figure 5 (left), which is equivalent to the graph in Figure 5 (right) if we remove allϵedges.
3
Model Querying and Transformation
UnQL [6] is a graph querying language based on struc-tural recursion, and has an expressive power of FO(TC) (first order with transitive closure), with time complexity of PTIME for graph querying. It has a friendly surface lan-guage with a select-where structure, with which users can write graph queries without explicit use of structural recur-sion. In this section, we review the graph querying language UnQL [6], show our extension of UnQL to UnQL+ for graph transformation (rather than just graph querying) [14],
and demonstrate how it is used for writing model transfor-mations.
3.1
Model Querying in UnQL
UnQL, like other query languages, has a convenient and powerfulselect-wherestructure for extracting information from a graph. We omit the formal definition of the language syntax, which can be found in [6]. For instance, the follow-ing query extracts all persistent classes from the class model in Figure 4, which is assumed to be bound by $classDB.
select$classwhere
{Association.(src|dest).Class: $class}in$classDB,
{is presistent :{Boolean:true}}in$class
The symbols prefixed with $ denote variables. This query returns all bindings of variable $class satisfying the two conditions in the where clause. The first condition is to find bindings of $class by matching theregular path pat-ternAssociation.(src|dest).Classwith the graph bound by $classDB, while the second condition is to ensure that the class is persistent.
3.2
Model Transformation in UnQL
+In model transformation, we often want to replace a sub-graph satisfying certain condition by another sub-graph. It is onerous to describe these kinds of graph transformations in UnQL because some context structure is required to be copied and propagated. UnQL+ is an extension of UnQL
with a newreplace-whereconstruct suitable for specifying model transformation. We illustrate our idea with some ex-amples, but omit the details which can be found in [14].
Consider that we want to add a prefix ofclass to each class name in the class model. We may write it with the replace-where structure by
replace{$name:{}}by{(”class”ˆ$name) :{}}where
{ ∗.Class.name.String:{$name:{}}}in$classDB whereˆdenotes string concatenation, and ∗ denotes ar-bitrary sequence of labels (in the path). The replace-where clause is similar to the select-where clause except that sub-graph to be replaced is bound by either a sub-graph variable $g or a pair of a label and graph variables{$l : $g}.
The replace-where construct can be used to define vari-ous model transformations such as extension of a subgraph with some new information and deletion of a subgraph sat-isfying a certain condition.
extend$gwith $g′where...
def
= replace$gby($g∪$g′)where...
delete$gwhere...
def
= replace$gby{}where...
3.3
Compositional Transformation
Unlike most rule-based model transformation languages where model transformation composition is not straightfor-wardly supported [9], UnQL+ is functional and
compo-sitional; model transformations are functions, and smaller model transformations are composed to form a bigger one.
Consider that we want to extract all persistent classes from the class model $classDB, and transform them to ta-bles by replacingattrsbycolsandAttribute byColumn. This can be described by composition of three transforma-tions, each corresponding to one step above.
(* replaceAttribute*)
replace{$lA: $g}by{Column: $g}where
$dbin
(* replaceattrs*)
(replace{$la : $A}by{cols: $A}where
$classin
(* select classes *)
(select$classwhere
{Association.(src|dest).Class : $class}
in$classDB,
{is presistent :{Boolean :true}}in$class),
{$la : $A}in$class,$la =attrs),
{cols:{$lA: $g}}in$db,$lA=Attribute
A more involved example and discussion on systematic development of ”big” model transformations with composi-tion can be found in Seccomposi-tion 6.
4
Desugaring UnQL
+to Graph Algebra
While UnQL+ is for users to write model
transforma-tions, UnCAL is its internal algebra for implementation, suitable for bidirectionalization and optimization.
4.1
Graph Constructors
There are nine data constructor which can be used to de-scribe construction of arbitrary graphs.
• {} (single node graph): it constructs a graph with a single node without an edge.
• {l : g} (singleton graph): it constructs a graph with the root pointing to the root of the graphgthrough the edgel.
• g1∪g2(union of graphs): it unions two graphs as
de-fined in Section 2.
• &x:=g(graph with input marker): it adds some input marker to the root ofg.
• &y(output node): it constructs a graph with a single node marked with one output marker.
• ()(empty graph): it constructs an empty graph which has neither node nor edge.
• g1⊕g2(disjoint union of graphs): it constructs a graph
by putting two graphs one next to the other horizon-tally.
• g1@g2(append of graphs): it connect the two graphs
vertically by connecting the output nodes of g1 with
corresponding input nodes ofg2.
• cycle(g) (cyclic graph): it connects the input nodes with the output nodes ofgto form cycles.
4.2
UnCAL: A Graph Algebra
UnCAL, as defined in Figure 6, has a set of graph con-structors and operators, by which arbitrary graphs can be represented and arbitrary graph transformation in UnQL+
can be described.
The first nine expression structures correspond to nine graph data constructors. They are used to describe graph construction. For instance, the graph in Figure 2 can be represented by the following UnCAL expression.
&z1@cycle(
(&z1:={a:{a: &z5}, b:{a: &z5}, c: &z4},
&z5:={d:{}},
&z4:={c: &z4}))
The most important operation for manipulating graphs in this algebra is structural recursion rec(λ(l, g).e), corre-sponding to the following functionh:
sfun h({l:g}) = e@h(g).
For any structural recursive function defined by
sfun f ({l:g}) = l⊙f(g)
f(v)can be represented in terms ofrecby
&z1@(rec(λ(l, g).(&z1:=l⊙&z1))(v)).
4.3
Mapping to UnCAL
UnQL+ can be fully transformed to UnCAL. UnQL+
E ::= {} | {L:E}
| E∪E
| &x:=E | &y
| ()
| E⊕E
| E@E
| cycle(E)
| Var
| ifBthenEelseE
| rec(λ(LabelVar,Var).E)(Var)
| letVar=EinE
Figure 6. UnCAL: A Graph Algebra
(2) eliminating the replace-where construct; (3) ing simple patterns to structural recursions; (4) transform-ing regular path patterns to mutual structural recursions; (5) tupling mutual structural recursions to single ones; and (6) mapping structural recursions to those in UnCAL. The de-tails of this mapping can be found in [14].
5
Bidirectional Evaluator
This section explains one of our important contributions, the first bidirectional interpretation of the graph algebra of UnCAL. The prototype system has been implemented in Objective Caml and the GUI interface for users to construct and modify graph models through the DOT and DOTTY system2, graph layout products developed by AT&T. In this section, we describe our bidirectional semantics for Un-CAL, and highlight how the system is implemented effi-ciently by automatic fusion.
5.1
Bidirectionalizing UnCAL
UnCAL can be bidirectionalized in the sense that a for-mal and sound bidirectional semantics can be given to Un-CAL, such that the forward computation performs the same as the usual UnCAL evaluator does, and the backward com-putation is guaranteed to satisfy the bidirectional properties [10] with respect to the forward computation.
5.1.1 Bidirectional Properties
Given an expression e and an environment ρ denoting a mapping from variables to values (a label or a graph), we define two computations: aforward computation
ρ ⇀ ge
2http://hoagland.org/Dot.html
is to evaluate the expressioneto a graphg under the envi-ronmentρ, while abackward computation
ρ′ ↽e ρ g′
is to compute a new environmentρ′ from the oldρand a
revised graph g′ over g obtained from forward
computa-tion. The forward and backward computations with respect to an expressioneshould satisfy the following two proper-ties [10].
• TheGetPutProperty: no change on the graph should give no change on the environment.
ρ ⇀ ge ρ ↽eρ g
• ThePutGetProperty: the backward computation com-putes a new environment ρ′ from g′ in such a way
that applying the forward computation underρ′again
should give the same graphg′.
ρ′ ↽eρ g′ ρ′ ⇀ ge ′
5.1.2 Bidirectional Interpretation of UnCAL
We give a set of rules to describe both forward and back-ward interpretation of expressions of UnCAL, which satisfy the bidirectional properties.
The rules for forward computation is summarized in Fig-ure 7. It is quite standard. We choose some to explain. The ruleFWD SGsays that a single graph expression{le:e}is evaluated by first computing the label expressionleand the graph expressioneunder the environmentρand then com-bining their results. The input marker rule (FWD I) says that the expression&x:=eis evaluated by first computing
eand get a disjoint union ofngraphsg1, . . . , gn wheregi
has the input marker of&yi, then the root node of this
dis-joint union is given a new input marker&yand the original input marker of&yiis renamed to a new marker&x.&yi.
Here the infix operator.is a Skolem function on markers which is associative, idempotent with respect to default in-put (root) marker&(&.&x= &x.& = &x), andinvertible. The most interesting rule isFWD RECfor evaluating struc-tural recursion. As explained in Section 2.2, it computes on each edge of the source graph in parallel and then combines the results.
The rules for backward computation is to reflect the change on the output back to the input by changing the bind-ing information of variables in the environment. The rules summarized in Figure 8, which guarantee the bidirectional properties.
ρ ⇀{} {} (FWD SN) ρ
le
⇀ l ρ ⇀ ge ρ {le⇀:e} {l:g}
(FWD SG) ρ
e1
⇀ g1 ρ
e2
⇀ g2
ρ e1⇀∪e2 g1∪g2
(FWD UNION)
ρ ⇀e (&y1:=g1, . . . ,&yn:=gn)
ρ &x⇀:=e &y:= (&x.&y1:=g1, . . . ,&x.&yn:=gn)
(FWD I) ρ &y
⇀ &y(FWD ON) ρ ⇀() ()(FWD EMP)
ρ ⇀e1 (g
11, . . . , g1m) ρ e2
⇀ (g21, . . . , g2n)
ρ e1⇀⊕e2 (g11, . . . , g1m, g21, . . . , g2n)
(FWD DUNION) ρ
e1
⇀ (g11, . . . , g1m) ρ e2
⇀ (g21, . . . , g2n)
ρ e1⇀@e2 (g
31, . . . , g3m)
(FWD APPEND)
ρ ⇀ ge ρ cycle⇀(e) cycle(g)
(FWD CYCLE) ρ v
⇀ ρ(v)(FWD VAR) ρ
b
⇀ true ρ ⇀ ge1 ρ if bthen⇀e1elsee2 g
(FWD IF)
for each{li:gi}inρ(v) : ρ[l←li, g←gi] e
⇀ gi
mergedG=merge(g1, . . . , gn)
ρ rec(λ(l,g⇀).e)(v) mergedG
(FWD REC)
ρ ⇀ ge1 1 ρ[v←g1]
e2
⇀ g2
ρ letv=⇀e1ine2 g 2
(FWD LET)
Figure 7. Forward Computation Rules
Rules BWD SN, BWD ON and BWD EMP indicate that a graph produced by the single node expression, the out-put marker expression, or the empty expression should have no effect on the environment because their forward computation does not depend on the environment. Rules BWD UNION, BWD DUNION, BWD APPEND, BWD REC first use the operator⇒to decompose the revised graph in such as way that each can be used for backward computa-tion with one of the subexpressions, and then unify the up-dated environments by⊎ρsuch asρ′1⊎ρρ′2. We make such
decomposition possible by associating graph nodes with information of where they come from during the forward computation. Because of this decomposition, these rules do not allow insertion of new edges. An output graph can be freely updated with insertion and deletion if it is computed from a variable in its forward computation, as seen in Rule BWD VAR.
One interesting rule is Rule BWD LETfor dealing with composition. It has two stages: performing backward com-putation fore2using the forward computation result ofe1
before performing backward computation fore1. This rule
shows the difference between bidirectional computation and inverse computation, where inverse computation does not need to use input.
As an example of backward computation where modifi-cation propagates to source, consider the following simple UnCAL expression in which the forward computation just prependresultedge to $classDB
let$v = $classDB in{result : $v}
and suppose the user modifies the “Phone” edge to “Tele-phone” on the result. Let this result be g’. During back-ward computation,BWD LETis invoked, which in tern in-vokes backward computation of{result : $v}(first stage
above) using environment ρ = [$classDB ← h,$v ←
h]. This invokes BWD SG which extract h′ from g′ by
removing topmost result edge and BWD VARreflects this modification back to the binding of $v. Going back to BWD LET, using the modified binding of $v as the new value of the expression $classDB, BWD VAR is invoked again (second stage above), which results in updated bind-ing of $classDB, the source graph. Lastly,⊎ρ unifies the
results of the two stages. In computing [$classDB ←
h′]⊎
[$classDB←h] [$classDB ← h], ⊎ knows that left
hand side indicates modification by comparing it with origi-nal value of $classDBin its subscript environment. We can thus obtain the updated graph by extracting this new binding from this resultant environment.
5.2
Optimization by Fusion
In our framework, consecutive model transformations are translated into composition of structural recursions in UnCAL. The composition may introduce unnecessary in-termediate graphs, but this efficiency can be removed by applying fusion transformation [6]. The following two rules are main fusion transformation rules for cascading rec’s. The first rule is applied whene2(l, t)does not depend ont,
while the second rule is applied otherwise.
rec(e2)◦rec(e1) =rec(rec(e2))◦e1
rec(e2)◦rec(e1)
=rec(λ(l, g).rec(e2)(e1(l, g)@rec(e1)(g)))
ρ {}↽ρ {}(BWD SN)
ρl le
↽ρ l′ ρe e
↽ρ g′
ρl⊎ρρe
{le:e}
↽ ρ {l′:g′}
(BWD SG) g ′⇒g′
1∪g′2 ρ1
e1
↽ρ g1′ ρ2
e2
↽ρ g2′
ρ1⊎ρρ2
e1∪e2
↽ ρ g′
(BWD UNION)
ρ′ ↽eρ (&y1:=g′1, . . . ,&yn:=g′n)
ρ′ &x↽:=e
ρ &y:= (&x.&y1:=g1′, . . . ,&x.&yn:=g′n)
(BWD I) ρ &y
↽ρ &y(BWD ON) ρ
()
↽ρ ()(BWD EMP)
ρ′
1
e1
↽ρ (g11′ , . . . , g1′m) ρ′2
e2
↽ρ (g21′ , . . . , g2′n)
ρ′1⊎ρρ′2
e1⊕e2
↽ ρ (g′11, . . . , g′1m, g21′ , . . . , g2′n)
(BWD DUNION)
(g′31, . . . , g′3m)⇒(g11′ , . . . , g1′m)@(g′21, . . . , g′2n)
ρ′1 ↽e1
ρ (g11′ , . . . , g1′m) ρ′2
e2
↽ρ (g21′ , . . . , g2′n)
ρ′
1⊎ρρ′2 e1@e2
↽ ρ (g31′ , . . . , g3′m)
(BWD APPEND)
ρ′ ↽eρ g′
ρ′ cycle↽(e)
ρ cycle(g′)
(BWD CYCLE)
ρ[v←g′] v
↽ρ g′
(BWD VAR)
ρ′ ↽e1
ρ g′ ρ′ ⇀b true
ρ′ ifbthen↽e1elsee2ρ g′
(BWD IF TRUE)
ρ′ e↽2
ρ g′ ρ′ ⇀b false
ρ′ ifbthen↽e1elsee2ρ g′
(BWD IF FALSE) g′⇒g′
1, . . . , gn′ ρ(v)⇒g1, . . . , gn
ρ′i ↽eρ[{l:g}←gi] g
′
i
ρ′=mergeEnv
ρ(ρ′1, . . . , ρ′n)
g′′=merge({ρ
1(l) :ρ1(g)}, . . . ,{{ρn(l) :ρn(g)})
ρ′′=ρ′[v←g′′]
ρ′′ rec(λ(l,g↽).e)(v)ρ g′
(BWD REC)
ρ ⇀ ge1 1 ρ′1
e2
↽ρ[v←g1] g′ ρ′
e1
↽ρ ρ′1(v) ρ′⊎ρ(ρ′1\v)
letv=e 1ine2 ↽ ρ g′
(BWD LET)
Figure 8. Backward Computation Rules
following rules to to moverecs close to each other.
rec(e)({}) = {}
rec(e)({l:d}) = e(l, d)@rec(e)(d)
rec(e)(d1∪d2) = rec(e)(d1)∪rec(e)(d2)
rec(e)(&x:=d) = &x·(rec(e)(d))
rec(e)() = ()
rec(e)(d1⊕d2) = rec(e)(d1)⊕rec(e)(d2)
gdoes not occur free ine
rec(λ(l, g).e)(d1@d2) =rec(e)(d1)@rec(e)(d2)
gdoes not occur free ine
rec(λ(l, g).e)(cycle(d)) =cycle(rec(e)(d))
6
An Application: Class2RDBMS
This section shows how we write an UnQL+ program for a practical model transformation,Class2RDBMS. It is a simplified version of the well known ”Class to RDBMS” which was proposed at [3] to compare and contrast various kinds of approaches to model transformations. We show how the model transformation can be systematically devel-oped in UnQL+after explaining the requirement of a model
transformation Class2RDBMS.
6.1
Specification of Class2RDBMS
Class2RDBMS is a model transformation from Class models, which has been explained in Section 2, to RDBMS
Figure 9. A RDBMS Model
models. For instance, it transforms the Class model in Fig-ure 3 into an RDBMS model in FigFig-ure 9. The corresponding RDBMS model should satisfy the following requirement. Class2RDBMS maps each persistent class in a Class model to a table in a RDBMS model. All attributes of the class or its subclasses are mapped to columns in the corresponding table. If a primary attribute belongs to the class, a pkey
pointing from the table to the corresponding column is es-tablished. If an attribute belongs to its subclass which is persistent, a foreign key to the corresponding table is es-tablished. Non-persistent classes are not mapped to tables, however. One of the main requirements for Class2RDBMS is to preserve all the information in the class diagram. That means all attributes of non-persistent subclasses are dis-tributed over those tables stemming from persistent classes which access non-persistent classes. Note that we repre-sent RDBMS models by edge-labelled graphs in UnQL+as
well as Class models. This model transformation is not triv-ial. We show below how to systematically develop it in our framework.
6.2
Class2RDBMS in UnQL
+The framework of UnQL+ allows us to develop
big-ger model transformations by gluing smaller transforma-tions via intermediate models, without worrying about in-efficiency due to the intermediate models. This is because unnecessary intermediate models will be removed automat-ically by our system. Figure 10 shows the whole transfor-mation of Class2RDBMS in UnQL+. Let us explain how it
is systematically developed.
We construct an UnQL+program for Class2RDBMS by
splitting its specification into two steps. On the first step, every persistent class is mapped to a table which is con-nected with its columns according to attributes of the class and its subclasses. All subclasses are collected by regular path patterns as shown in Section 3.1. If necessary, refer-encespkeyandfkeysare added by anextendconstruct in UnQL+, provided that referencesrefsofFkeydo not point to the referring table because the table may not have been constructed yet. They point to the name of the refer-ring table instead. On the second step, each name pointed byrefsis replaced by the corresponding table by using a
replaceconstruct.
Our framework allows us to modify on the target model RDBMS. The modification is reflected to the source model Class. For example, we can modify string values (e.g.,
"Person" and"addr") in the RDBMS model in Fig-ure 9.
7
Related Work
Besides the related work in the introduction, we high-light some others that are related to graph-based model transformation, graph querying, and linguistic approach to bidirectional programming.
Our work is much related to research on model trans-formation based on graph transtrans-formation [9, 22, 17]. AGG [26] is a well-known rule-based visual tool that supports typed (attributed) graph transformations including type inheritance and multiplicities. Triple Graph Grammars (TGG) [19, 12] is an extension of Pratt’s pair grammar approach [23], which aims at the declarative specification of model to model integration rules. Different from these approach which are rule-based, our approach is function-based, using graph algebras for graph construction, model transformation composition for systematic development, and model transformation manipulation for automatic op-timization.
Our work was greatly influenced by interesting work on efficient graph querying [24, 6]. Unlike trees, graphs have subtle issues on their representation and their equiva-lence. The use of bisimulation and structural recursion in [6] opens a new way to build a framework for both declara-tive and efficient graph querying with high modularity and composability. This motivated us to extend the framework from graph querying to graph transformation and apply it to model transformation.
This work has been inspired by recent work on linguis-tic approach to bidirectionalization of tree transformation [10, 21, 4, 16] for tree data synchronization. One impor-tant feature of these systems is a clear bidirectional se-mantics, which, however, does not exist in most existing bidirectional model transformation systems [22, 25]. Al-though some attempts have been made [27, 2], it remains as a challenge to provide a general bidirectional framework for graphs, and our this work is a big step to this direction.
8
Conclusions
In this paper, we propose a novel algebraic framework to support systematic development of bidirectional model transformation. Different from many existing frameworks that are rule-based, our framework is functional and alge-braic, which is based on a graph algebra and structural re-cursion. Our new framework supports systematic develop-ment of model transformations in a compositional manner, has a clear semantics for bidirectional model transforma-tion, and can be efficiently implemented.
This work is our first step towardsbidirectional model programming, a linguistic framework to support systematic development of model transformation programs. In the fu-ture, we wish to look more into relation between the rule-based approach and the algebraic and functional approach, and see how to integrate them to have a more powerful framework for bidirectional model transformation.
Acknowledgements
We would like to thank Mary Fernandez from AT&T Labs Research, who kindly provided us with the SML source codes of an UnQL system, which helped us a lot in implementing our extended system in OCaml.
select $tables where $tables in
(select $tables where
{Class:$class} in (select $assoc where {Association.(src|dest):$assoc} in $db), {is_persistent.Boolean:true} in $class,
$dests in (select {Class:$dest} where {(src_of.Association.dest.Class)+:$dest} in $class), $related in ({Class:$class} U $dests),
$cols in (select {cols:{Column:{name:$n,type:$t}}} where {Class.attrs.Attribute:{name:$n,type:$t}} in $related), $tables in (select {Table:{name:$cname} U $cols} where {name:$cname} in $class),
$tables in (extend $table with $pkeys U $fkeys where {Table:$table} in $tables,
{cols:$cols} in $table,
{Column.name.String:{$cname:{}}} in $cols, $pkeys in (select {pkey:$cols} where
{attrs.Attribute: {is_primary.Boolean:true, name.String:{$pname:{}}}} in $class, $cname = $pname),
$fkeys in (select {fkeys:{Fkey:{cols:$cols, ref:$ref}}} where {Class:{is_persistent.Boolean:true,
attrs.Attribute.name.String:{$aname:{}}, name:$ref}} in $dests, $cname = $aname))),
$tables in (replace $ref by {Table:$table} where
{Table.fkeys.Fkey.ref:$ref, Table:$table} in $tables, {String:{$rname:{}}} in $ref,
{name.String:{$tname:{}}} in $table, $tname = $rname)
Figure 10. Class2RDBMS in UnQL+
References
[1] M. Antkiewicz and K. Czarnecki. Framework-specific mod-eling languages with round-trip engineering. InMoDELS 2006: Proceedings of the 9th nternational Conference on Model Driven Engineering Languages and Systems, pages 692–706. Springer-Verlag, 2006.
[2] M. Antkiewicz and K. Czarnecki. Design space of heteroge-neous synchronization. InGTTSE ’07: Proceedings of the 2nd Summer School on Generative and Transformational Techniques in Software Engineering, 2007.
[3] J. Bezivin, B. Rumpe, and T. L. Sch¨urr A. Model transfor-mation in practice workshop announcement. InMTiP 2005, International Workshop on Model Transformations in Prac-tice. Springer-Verlag, 2005.
[4] A. Bohannon, J. N. Foster, B. C. Pierce, A. Pilkiewicz, and A. Schmitt. Boomerang: resourceful lenses for string data. In G. C. Necula and P. Wadler, editors,POPL, pages 407– 419. ACM, 2008.
[5] P. Braun and F. Marschall. BOTL : The bidirectional object oriented transformation language. Technical Report TUM-I0307, Technische Universit¨at Mu¨nchen, 2003.
[6] P. Buneman, M. F. Fernandez, and D. Suciu. UnQL: a query language and algebra for semistructured data based on struc-tural recursion. VLDB Journal: Very Large Data Bases, 9(1):76–110, 2000.
[7] K. Czarnecki and S. Helsen. Classification of model trans-formation approaches. InWorkshop on Generative Tech-niques in the Context of Model-Driven Architecture, 2003. [8] H. Ehrig, K. Ehrig, C. Ermel, F. Hermann, and G. Taentzer.
Information preserving bidirectional model transformations. InFundamental Approaches to Software Engineering, pages 72–86. 2007.
[9] K. Ehrig, E. Guerra, J. de Lara, L. Lengyel, T. Leven-dovszky, U. Prange, G. Taentzer, D. Varr´o, and S.
Varr´o-Gyapay. Model transformation by graph transformation: A comparative study. InMTiP 2005, International Workshop on Model Transformations in Practice. Springer-Verlag, 2005.
[10] J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bi-directional tree transforma-tions: a linguistic approach to the view update problem. In
POPL ’05 : ACM SIGPLAN–SIGACT Symposium on Prin-ciples of Programming Languages, pages 233–246, 2005. [11] M. Garcia. Bidirectional synchronization of multiple views
of software models. InProceedings of DSML-2008, volume 324 ofCEUR-WS, pages 7–19, 2008.
[12] H. Giese and R. Wagner. Incremental model synchronization with triple graph grammars. In O. Nierstrasz, J. Whittle, D. Harel, and G. Reggio, editors,Models ’06: Proc. of the 9th International Conference on Model Driven Engineering Languages and Systems, volume 4199 ofLNCS, pages 543– 557. Springer Verlag, October 2006.
[13] J. Grundy, J. Hosking, and W. B. Mugridge. Inconsistency management for multiple-view software development envi-ronments.IEEE Trans. Softw. Eng., 24(11):960–981, 1998. [14] S. Hidaka, Z. Hu, H. Kato, and K. Nakano. Towards
com-postional approach to model transformations for software development. Technical Report GRACE-TR08-01, GRACE Center, National Institute of Informatics, Aug. 2008. [15] Z. Hu, H. Iwasaki, M. Takeichi, and A. Takano. Tupling
calculation eliminates multiple data traversals. InACM SIG-PLAN International Conference on Functional Program-ming (ICFP’97), pages 164–175, Amsterdam, The Nether-lands, June 1997. ACM Press.
[16] Z. Hu, S.-C. Mu, and M. Takeichi. A programmable editor for developing structured documents based on bidirectional transformations.Higher-Order and Symbolic Computation, 21(1-2):89–118, 2008.
[17] F. Jouault and I. Kurtev. Transforming models with ATL. In
Proceedings of Satellite Events at the MoDELS 2005 Con-ference, pages 128–138. LNCS 3814, Springer, 2006. [18] F. Klar, A. K¨onigs, and A. Sch¨urr. Model
transforma-tion in the large. In I. Crnkovic and A. Bertolino, editors,
ESEC/SIGSOFT FSE, pages 285–294. ACM, 2007.
[19] A. Konigs and A. Schurr. Tool integration with triple graph grammars - a survey. Electronic Notes in Theoretical Com-puter Science, 148(1):113–150, February 2006.
[20] R. L¨ammel. Coupled Software Transformations (Extended Abstract). InFirst International Workshop on Software Evo-lution Transformations, Nov. 2004.
[21] K. Matsuda, Z. Hu, K. Nakano, M. Hamana, and a. Masato Takeichi. Bidirectionalization transformation based on automatic derivation of view complement func-tions. In12th ACM SIGPLAN International Conference on Functional Programming (ICFP 2007), pages 47–58. ACM Press, Oct. 2007.
[22] OMG. MOF QVT final adopted specification. http://
www.omg.org/docs/ptc/05-11-01.pdf, 2005.
[23] T. W. Pratt. Pair grammars, graph languages and string-to-graph translations. J. Comput. Syst. Sci., 5(6):560–595, 1971.
[24] L. Sheng, Z. M. Ozsoyoglu, and G. Ozsoyoglu. A graph query language and its query processing. InICDE, pages 572–581, 1999.
[25] P. Stevens. Bidirectional model transformations in QVT: Se-mantic issues and open questions. In G. Engels, B. Opdyke, D. C. Schmidt, and F. Weil, editors,Proc. 10th MoDELS, volume 4735 ofLecture Notes in Computer Science, pages 1–15. Springer, 2007.
[26] G. Taentzer. AGG: A graph transformation environment for modeling and validation of software. In J. L. Pfaltz, M. Nagl, and B. B¨ohlen, editors, AGTIVE, volume 3062 of LNCS, pages 446–453. Springer, 2003.
